{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Invalid Transactions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: invalidTransactions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #查询无效交易"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果出现下述两种情况，交易 <strong>可能无效</strong>：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>交易金额超过<meta charset=\"UTF-8\" />&nbsp;<code>$1000</code></li>\n",
    "\t<li>或者，它和&nbsp;<strong>另一个城市</strong>&nbsp;中 <strong>同名</strong> 的另一笔交易相隔不超过 <code>60</code> 分钟（包含 60 分钟整）</li>\n",
    "</ul>\n",
    "\n",
    "<p>给定字符串数组交易清单<meta charset=\"UTF-8\" />&nbsp;<code>transaction</code>&nbsp;。每个交易字符串&nbsp;<code>transactions[i]</code>&nbsp;由一些用逗号分隔的值组成，这些值分别表示交易的名称，时间（以分钟计），金额以及城市。</p>\n",
    "\n",
    "<p>返回&nbsp;<code>transactions</code>，返回可能无效的交易列表。你可以按 <strong>任何顺序</strong> 返回答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>transactions = [\"alice,20,800,mtv\",\"alice,50,100,beijing\"]\n",
    "<strong>输出：</strong>[\"alice,20,800,mtv\",\"alice,50,100,beijing\"]\n",
    "<strong>解释：</strong>第一笔交易是无效的，因为第二笔交易和它间隔不超过 60 分钟、名称相同且发生在不同的城市。同样，第二笔交易也是无效的。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>transactions = [\"alice,20,800,mtv\",\"alice,50,1200,mtv\"]\n",
    "<strong>输出：</strong>[\"alice,50,1200,mtv\"]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>transactions = [\"alice,20,800,mtv\",\"bob,50,1200,mtv\"]\n",
    "<strong>输出：</strong>[\"bob,50,1200,mtv\"]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>transactions.length &lt;= 1000</code></li>\n",
    "\t<li>每笔交易&nbsp;<code>transactions[i]</code>&nbsp;按&nbsp;<code>\"{name},{time},{amount},{city}\"</code>&nbsp;的格式进行记录</li>\n",
    "\t<li>每个交易名称&nbsp;<code>{name}</code>&nbsp;和城市&nbsp;<code>{city}</code>&nbsp;都由小写英文字母组成，长度在&nbsp;<code>1</code>&nbsp;到&nbsp;<code>10</code>&nbsp;之间</li>\n",
    "\t<li>每个交易时间&nbsp;<code>{time}</code>&nbsp;由一些数字组成，表示一个&nbsp;<code>0</code>&nbsp;到&nbsp;<code>1000</code>&nbsp;之间的整数</li>\n",
    "\t<li>每笔交易金额&nbsp;<code>{amount}</code>&nbsp;由一些数字组成，表示一个&nbsp;<code>0</code> 到&nbsp;<code>2000</code>&nbsp;之间的整数</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [invalid-transactions](https://leetcode.cn/problems/invalid-transactions/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [invalid-transactions](https://leetcode.cn/problems/invalid-transactions/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"alice,20,800,mtv\",\"alice,50,100,beijing\"]', '[\"alice,20,800,mtv\",\"alice,50,1200,mtv\"]', '[\"alice,20,800,mtv\",\"bob,50,1200,mtv\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, t: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        used = set()\n",
    "        for i in range(len(t)):\n",
    "            for j in range(len(t)):\n",
    "                if i==j:\n",
    "                    continue\n",
    "                a, b = t[i].split(','), t[j].split(',')\n",
    "                if int(a[2])>1000:\n",
    "                    if i not in used:\n",
    "                        ans.append(t[i])\n",
    "                        used.add(i)\n",
    "                elif a[0]==b[0] and a[3]!=b[3] and abs(int(a[1])-int(b[1]))<=60:\n",
    "                    if i not in used:\n",
    "                        ans.append(t[i])\n",
    "                        used.add(i)\n",
    "                    if j not in used:\n",
    "                        ans.append(t[j])\n",
    "                        used.add(j)\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "    #def invalidTransactions(transactions):\n",
    "        invalid = []\n",
    "        for i in range(len(transactions)):\n",
    "            name, time, amount, city = transactions[i].split(',')\n",
    "            time = int(time)\n",
    "            amount = int(amount)\n",
    "            if amount > 1000:\n",
    "                invalid.append(transactions[i])\n",
    "            else:\n",
    "                for j in range(len(transactions)):\n",
    "                    if i != j:\n",
    "                        other_name, other_time, other_amount, other_city = transactions[j].split(',')\n",
    "                        other_time = int(other_time)\n",
    "                        other_amount = int(other_amount)\n",
    "                        if name == other_name and abs(time - other_time) <= 60 and city != other_city:\n",
    "                            invalid.append(transactions[i])\n",
    "                            break\n",
    "        return invalid\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, t: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for i in range(len(t)):\n",
    "            a = t[i].split(',')\n",
    "            if int(a[2])>1000:\n",
    "                ans.append(t[i])\n",
    "                continue\n",
    "            for j in range(len(t)):\n",
    "                if i==j:\n",
    "                    continue\n",
    "                b = t[j].split(',')\n",
    "                if a[0]==b[0] and a[3]!=b[3] and abs(int(a[1])-int(b[1]))<=60:\n",
    "                    ans.append(t[i])\n",
    "                    break\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        hashmap = {}\n",
    "\n",
    "        res = set()\n",
    "\n",
    "        for index, t in enumerate(transactions):\n",
    "            name, time, amount, city = t.split(',')\n",
    "            if name not in hashmap:\n",
    "                hashmap[name] = []\n",
    "                if int(amount) > 1000:\n",
    "                    res.add(index)\n",
    "            else:\n",
    "                prevTrans = hashmap[name]\n",
    "                for j in range(len(prevTrans)):\n",
    "                    prevName, prevTime, prevAmount, prevCity = transactions[prevTrans[j]].split(',')\n",
    "                    if int(amount) > 1000:\n",
    "                        res.add(index)\n",
    "                    if abs(int(time) - int(prevTime)) <= 60 and city != prevCity:\n",
    "                        res.add(index)\n",
    "                        res.add(prevTrans[j])\n",
    "            hashmap[name].append(index)\n",
    "\n",
    "        return [transactions[t] for t in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        n=len(transactions)\n",
    "        tag=[0]*n\n",
    "        res=[]\n",
    "        for i in range(n):\n",
    "            ti=transactions[i][1:-1].split(\",\")\n",
    "            for j in range(n):\n",
    "                tj=transactions[j][1:-1].split(\",\")\n",
    "                if int(ti[2])>1000 or (ti[0]==tj[0] and ti[3]!=tj[3] and abs(int(ti[1])-int(tj[1]))<=60):\n",
    "                    res.append(transactions[i])\n",
    "                    tag[i]=1\n",
    "                    break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        # groups = defaultdict(list)\n",
    "        # ans = set()\n",
    "        # for t in transactions:\n",
    "        #     name,time,amount,city = t.split(\",\")\n",
    "        #     if int(amount) > 1000:\n",
    "        #         ans.add(t)\n",
    "        \n",
    "        #     for x,y,t0 in groups[name]:\n",
    "        #         if abs(y-int(time)) <=60 and x!=city:\n",
    "        #             ans.add(t)\n",
    "        #             ans.add(t0)\n",
    "        \n",
    "        #     groups[name].append([city,int(time),t])\n",
    "        # return list(ans)\n",
    "        n = len(transactions)\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            name,time,amount,city = transactions[i].split(\",\")\n",
    "            if int(amount)>1000:\n",
    "                ans.append(transactions[i])\n",
    "                continue\n",
    "            for j in range(n):\n",
    "                if i!=j:\n",
    "                    name1,time1,amount1,city1 = transactions[j].split(\",\")\n",
    "                    if name==name1 and city!=city1 and abs(int(time)-int(time1))<=60:\n",
    "                        ans.append(transactions[i])\n",
    "                        break\n",
    "        return ans\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        name = defaultdict(list)\n",
    "        ans = set()\n",
    "        for i, trans in enumerate(transactions):\n",
    "            n,t,m,c = trans.split(',')\n",
    "            if int(m) > 1000:\n",
    "                ans.add(i)\n",
    "            if n in name:\n",
    "                for j, tt, cc in name[n]:\n",
    "                    if abs(int(t) - tt) <= 60 and cc != c:\n",
    "                        ans.add(i)\n",
    "                        ans.add(j)\n",
    "\n",
    "            name[n].append((i, int(t), c))\n",
    "            \n",
    "        return [transactions[i] for i in ans]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "        for i, s in enumerate(transactions):\n",
    "            n, t, p, d = s.split(',')\n",
    "            if int(p) > 1000:\n",
    "                ans.append(s)\n",
    "                continue\n",
    "            for j, u in enumerate(transactions):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                else:\n",
    "                    n2, t2, p2, d2 = u.split(',')\n",
    "                    if n == n2 and d != d2 and abs(int(t) - int(t2)) <= 60:\n",
    "                        ans.append(s)\n",
    "                        break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        parsed_transactions = [\n",
    "            {\n",
    "                \"name\": t.split(\",\")[0],\n",
    "                \"time\": int(t.split(\",\")[1]),\n",
    "                \"amount\": int(t.split(\",\")[2]),\n",
    "                \"city\": t.split(\",\")[3],\n",
    "                \"raw\": t\n",
    "            }\n",
    "            for t in transactions\n",
    "        ]\n",
    "        \n",
    "        transactions_by_name = {}\n",
    "        for t in parsed_transactions:\n",
    "            if t[\"name\"] not in transactions_by_name:\n",
    "                transactions_by_name[t[\"name\"]] = []\n",
    "            transactions_by_name[t[\"name\"]].append(t)\n",
    "        \n",
    "        invalid_transactions = []\n",
    "        \n",
    "        for name, trans in transactions_by_name.items():\n",
    "            for i, t in enumerate(trans):\n",
    "                if t[\"amount\"] > 1000:\n",
    "                    invalid_transactions.append(t[\"raw\"])\n",
    "                    continue\n",
    "                \n",
    "                for j, other_t in enumerate(trans):\n",
    "                    if i != j and abs(t[\"time\"] - other_t[\"time\"]) <= 60 and t[\"city\"] != other_t[\"city\"]:\n",
    "                        invalid_transactions.append(t[\"raw\"])\n",
    "                        break\n",
    "        \n",
    "        return invalid_transactions\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        # 名字：[（城市，时间，下标）]\n",
    "        tran = defaultdict(list)\n",
    "        ans = set() # 储存下标\n",
    "        for i, s in enumerate(transactions):\n",
    "            name, time, money, city = s.split(',')\n",
    "            time = int(time)\n",
    "            for c2, t2, j in tran[name]:\n",
    "                if c2 != city and abs(time - t2) <= 60:\n",
    "                    ans.update((i, j))\n",
    "                    \n",
    "            if int(money) > 1000:\n",
    "                ans.add(i)\n",
    "            tran[name].append((city, time, i))\n",
    "        return [transactions[i] for i in ans]\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        d = {}\n",
    "        for t in transactions:\n",
    "            arr = t.split(\",\")\n",
    "            name = arr[0]\n",
    "            time = int(arr[1])\n",
    "            amount = int(arr[2])\n",
    "            city = arr[3]\n",
    "            if d.get(name)==None:\n",
    "                d[name] = []\n",
    "            d[name].append([time,amount,city])\n",
    "        \n",
    "        ret = []\n",
    "        for k,v in d.items():\n",
    "            v.sort()\n",
    "            for i in range(len(v)):\n",
    "                Found = False\n",
    "                for j in range(i+1,len(v)):\n",
    "                    if v[i][0]+60<v[j][0]:\n",
    "                        break\n",
    "                    if v[j][2]!=v[i][2]:\n",
    "                        if len(v[j])<4:\n",
    "                            v[j].append(False)\n",
    "                            ret.append(\",\".join([k,str(v[j][0]),str(v[j][1]),v[j][2]]))\n",
    "                        Found = True\n",
    "                if (Found or v[i][1]>1000) and len(v[i])<4:\n",
    "                    v[i].append(False)\n",
    "                    ret.append(\",\".join([k,str(v[i][0]),str(v[i][1]),v[i][2]]))\n",
    "        \n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        invalid = set()\n",
    "        d = defaultdict(list)\n",
    "        for i, t in enumerate(transactions):\n",
    "            name, time, amount, city = t.split(',')\n",
    "            time = int(time)\n",
    "            amount = int(amount)\n",
    "            if amount > 1000:\n",
    "                invalid.add(i)\n",
    "            d[name].append((time, city, i))\n",
    "        \n",
    "        for v in d.values():\n",
    "            v.sort()\n",
    "            cnt = Counter()\n",
    "            left = 0\n",
    "            for right, (time, city, i) in enumerate(v):\n",
    "                while time > v[left][0] + 60:\n",
    "                    left_city = v[left][1]\n",
    "                    cnt[left_city] -= 1\n",
    "                    if cnt[left_city] == 0:\n",
    "                        del cnt[left_city]\n",
    "                    left += 1\n",
    "                cnt[city] += 1\n",
    "                if len(cnt) > 1:\n",
    "                    for j in range(left, right+1):\n",
    "                        invalid.add(v[j][2])\n",
    "        \n",
    "        return [transactions[i] for i in invalid]\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        arr, res = [], set()\n",
    "\n",
    "        for s in transactions:\n",
    "            name, time, money, city = s.split(',')\n",
    "            arr.append((name, int(time), int(money), city, s))\n",
    "\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            flag = False\n",
    "            for j in range(i + 1, n):\n",
    "                if arr[i][0] == arr[j][0] and arr[i][3] != arr[j][3] \\\n",
    "                    and abs(arr[i][1] - arr[j][1]) <= 60:\n",
    "                    res.add(j)\n",
    "                    flag = True\n",
    "            if flag or arr[i][2] > 1000: res.add(i)\n",
    "            \n",
    "        return [arr[i][-1] for i in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        res = set()\n",
    "        transactionMap = {}\n",
    "\n",
    "        # sorted_transactions = sorted(transactions, key= lambda x:x.split(',')[1] )\n",
    "\n",
    "        for  idx, transaction in enumerate(transactions):\n",
    "            name, time, amount, city = transaction.split(\",\")\n",
    "            time, amount = int(time), int(amount)\n",
    "            if amount > 1000:\n",
    "                res.add(idx) \n",
    "\n",
    "            if name not in transactionMap:\n",
    "                transactionMap[name] = [(time, city, transaction, idx)] # value should be a list \n",
    "            else:\n",
    "                for prev_time, prev_city, prev_transaction, prev_idx in transactionMap[name]:\n",
    "                    if prev_city != city and abs(time - prev_time )<= 60:\n",
    "                        res.add(idx)\n",
    "                        res.add(prev_idx)\n",
    "                \n",
    "                transactionMap[name].append((time, city,transaction, idx))\n",
    "        return [transactions[i] for i in res]\n",
    "        \n",
    "        \n",
    "        \n",
    "# 啊，这个答案还有可能有duplicate transaction ...\n",
    "# 如何改进我的方案？其实amount是没有必要记录在map里面的，但是，我们是有必要记录下来每一条transaction对应的index\n",
    "# 为什么？因为可能存在看起来一摸一样，但是是两条单独的transaction的情况！那我们可以\n",
    "\n",
    "\n",
    "# tricky：遍历 transactions = [\"aa\", \"aaa\", \"aa\", \"aaa\"] \n",
    "# 卡壳的地方：[\"alice,20,800,mtv\",\"alice,50,100,beijing\"] - 如何根据time进行排列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        result = set()\n",
    "        mapping = {}\n",
    "        for i,transaction in enumerate(transactions):\n",
    "            name, time, amount, city = transaction.split(',')\n",
    "            if(int(amount) > 1000):\n",
    "                result.add(i)\n",
    "            if(name not in mapping):\n",
    "                mapping[name] = []\n",
    "            mapping[name].append([int(time),city,i])\n",
    "        for name in mapping:\n",
    "            tmp = sorted(mapping[name], key=lambda x:[x[0],x[1]])\n",
    "            for i in range(len(tmp)):\n",
    "                for j in range(i-1,-1,-1):\n",
    "                    if(tmp[i][0]-tmp[j][0] <= 60 and tmp[i][1] != tmp[j][1]):\n",
    "                        result.add(tmp[i][2])\n",
    "                        result.add(tmp[j][2])\n",
    "                    if(tmp[i][0]-tmp[j][0] > 60):\n",
    "                        break\n",
    "        return [transactions[i] for i in result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        trans = [x.split(\",\") for x in transactions]\n",
    "        res = []\n",
    "        for i in range(len(trans)):\n",
    "            name, time, money, city = trans[i]\n",
    "            time = int(time)\n",
    "            if int(money) > 1000:\n",
    "                res.append(transactions[i])\n",
    "                continue\n",
    "            for j in range(len(trans)):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                n, t, m, c = trans[j]\n",
    "                if name == n and city != c and abs(int(t) - time) <= 60:\n",
    "                    res.append(transactions[i])\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, tr: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        m = len(tr)\n",
    "        vis = [False] * m\n",
    "        \n",
    "        for i in range(m):\n",
    "            tr[i] = tr[i].split(',')\n",
    "        \n",
    "        for i, (n, t, a, c) in enumerate(tr):\n",
    "            a = int(a)\n",
    "            if a > 1000:\n",
    "                o = ','.join(tr[i])\n",
    "                res.append(o)\n",
    "                vis[i] = True\n",
    "        \n",
    "        for i in range(m):\n",
    "            n, t, a, c = tr[i]\n",
    "            t = int(t)\n",
    "            a = int(a)\n",
    "            for j in range(i + 1, m):\n",
    "                n1, t1, a1, c1 = tr[j]\n",
    "                t1 = int(t1)\n",
    "                a1 = int(a1)\n",
    "                if n1 == n and abs(t1 - t) <= 60 and c1 != c:\n",
    "                    o = ','.join(tr[i])\n",
    "                    o1 = ','.join(tr[j])\n",
    "                    if not vis[i]:\n",
    "                        res.append(o)\n",
    "                        vis[i] = True\n",
    "                    if not vis[j]:\n",
    "                        res.append(o1)\n",
    "                        vis[j] = True\n",
    "        return res\n",
    "                \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        result = set()\n",
    "        mapping = {}\n",
    "        for i,transaction in enumerate(transactions):\n",
    "            name, time, amount, city = transaction.split(',')\n",
    "            if(int(amount) > 1000):\n",
    "                result.add(i)\n",
    "            if(name not in mapping):\n",
    "                mapping[name] = []\n",
    "            mapping[name].append([int(time),city,i])\n",
    "        for name in mapping:\n",
    "            tmp = sorted(mapping[name], key=lambda x:[x[0],x[1]])\n",
    "            for i in range(len(tmp)):\n",
    "                for j in range(i-1,-1,-1):\n",
    "                    if(tmp[i][0]-tmp[j][0] <= 60 and tmp[i][1] != tmp[j][1]):\n",
    "                        result.add(tmp[i][2])\n",
    "                        result.add(tmp[j][2])\n",
    "                    if(tmp[i][0]-tmp[j][0] > 60):\n",
    "                        break\n",
    "        return [transactions[i] for i in result]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        user_transaction = defaultdict(list)\n",
    "        res = list()\n",
    "        for transaction in transactions:\n",
    "            item = transaction.split(',')\n",
    "            user_transaction[item[0]].append(item[1:])\n",
    "        \n",
    "        for key, v in user_transaction.items():\n",
    "            for i in range(len(v)):\n",
    "                if int(v[i][1]) > 1000:\n",
    "                    res.append(f'{key},{\",\".join(v[i])}')\n",
    "                    continue \n",
    "                for j in range(len(v)):\n",
    "                    if i != j and abs(int(v[i][0]) - int(v[j][0])) <= 60 and v[i][-1] != v[j][-1]:\n",
    "                        res.append(f'{key},{\",\".join(v[i])}')\n",
    "                        break \n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        transactions=[i.split(\",\") for i in transactions]\n",
    "        res=[]\n",
    "        for i,v in enumerate(transactions):\n",
    "            if int(v[2])>1000:\n",
    "                res.append(\",\".join(v))\n",
    "                continue\n",
    "            for j,u in enumerate(transactions):\n",
    "                if i==j:\n",
    "                    continue\n",
    "                if v[0]==u[0] and v[3]!=u[3] and abs(int(v[1])-int(u[1]))<=60:\n",
    "                    res.append(\",\".join(v))\n",
    "                    break\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        user_transaction = defaultdict(list)\n",
    "        res = list()\n",
    "        for transaction in transactions:\n",
    "            item = transaction.split(',')\n",
    "            user_transaction[item[0]].append(item[1:])\n",
    "        \n",
    "        for key, v in user_transaction.items():\n",
    "            for i in range(len(v)):\n",
    "                if int(v[i][1]) > 1000:\n",
    "                    res.append(f'{key},{\",\".join(v[i])}')\n",
    "                    continue \n",
    "                for j in range(len(v)):\n",
    "                    if i != j and abs(int(v[i][0]) - int(v[j][0])) <= 60 and v[i][-1] != v[j][-1]:\n",
    "                        res.append(f'{key},{\",\".join(v[i])}')\n",
    "                        break \n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        trans = [x.split(',') for x in transactions]\n",
    "        res = []\n",
    "        for i in range(len(trans)):\n",
    "            name, time, money, city = trans[i]\n",
    "            time = int(time)\n",
    "            if int(money) > 1000:\n",
    "                res.append(transactions[i])\n",
    "                continue\n",
    "            for j in range(len(trans)):\n",
    "                if i == j:\n",
    "                    continue;\n",
    "                name1, time1, money1, city1 = trans[j]\n",
    "                if name1 == name and city1 != city and abs(int(time1) - time) <= 60:\n",
    "                    res.append(transactions[i])\n",
    "                    break;\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Build a hash table that maps (time, name) to the cities of the transactions that happened at the given time and by the given person.\n",
    "    Then for each transaction, check if it is invalid:\n",
    "        1. If the amount is greater than 1000, it is invalid.\n",
    "        2. If there is another transaction by the same person within 60 minutes and in a different city, it is invalid.\n",
    "    Time complexity: O(n). Space complexity: O(n).\n",
    "    '''\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        mapping = {}\n",
    "        for transaction in transactions:\n",
    "            name, time, _, city = transaction.split(',')\n",
    "            time = int(time)\n",
    "            mapping.setdefault((time, name), set()).add(city) # use set to avoid duplicates\n",
    "        \n",
    "        invalid = []\n",
    "        for transaction in transactions:\n",
    "            name, time, amount, city = transaction.split(',')\n",
    "            time, amount = int(time), int(amount)\n",
    "            if amount > 1000:\n",
    "                invalid.append(transaction)\n",
    "                continue\n",
    "\n",
    "            for other_time in range(time - 60, time + 61):\n",
    "                if (other_time, name) not in mapping:\n",
    "                    continue\n",
    "                if (len(mapping[(other_time, name)]) > 1 or # the set contains more than one element -> there are transactions in different cities\n",
    "                    next(iter(mapping[(other_time, name)])) != city): # get the only element in the set\n",
    "                    invalid.append(transaction)\n",
    "                    break\n",
    "        return invalid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        vec = [s.split(\",\") for s in transactions]\n",
    "        res = []\n",
    "        L = len(vec)\n",
    "        isOK = [True] * L \n",
    "        # print(vec)\n",
    "        for i in range(L):\n",
    "            if int(vec[i][2])>1000:# or isOK[i]==False: \n",
    "                isOK[i] = False\n",
    "                #continue\n",
    "            #print(vec[i])\n",
    "            for j in range(i + 1, L):\n",
    "                if vec[i][0]==vec[j][0] and vec[i][3]!=vec[j][3] and abs(int(vec[i][1])-int(vec[j][1]))<=60:\n",
    "                    #print(vec[i][0], vec[j][3], vec[j][3], vec[j][3])\n",
    "                    isOK[i] = isOK[j] = False\n",
    "        \n",
    "        res = [transactions[i] for i in range(L) if isOK[i]==False]\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        # 名字：[（城市，时间，下标）]\n",
    "        tran = defaultdict(list)\n",
    "        ans = set() # 储存下标\n",
    "        for i, s in enumerate(transactions):\n",
    "            name, time, money, city = s.split(',')\n",
    "            time = int(time)\n",
    "            for c2, t2, j in tran[name]:\n",
    "                if c2 != city and abs(time - t2) <= 60:\n",
    "                    ans.update((i, j))\n",
    "                    \n",
    "            if int(money) > 1000:\n",
    "                ans.add(i)\n",
    "            tran[name].append((city, time, i))\n",
    "        return [transactions[i] for i in ans]\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        res = set()\n",
    "        dic = {}\n",
    "        for idx, transaction in enumerate(transactions):\n",
    "            name, time, amount, city = transaction.split(',')\n",
    "            if int(amount) > 1000:\n",
    "                res.add(idx)\n",
    "\n",
    "            if name not in dic:\n",
    "                dic[name] = [(idx, time, amount, city)]\n",
    "            else:\n",
    "                for item in dic[name]:\n",
    "                    if city != item[3] and abs(int(time) - int(item[1])) <= 60:\n",
    "                        res.add(idx)\n",
    "                        res.add(item[0])\n",
    "                dic[name].append((idx, time, amount, city))\n",
    "        return [transactions[_] for _ in res]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        ans = [tran.split(\",\") for tran in transactions]\n",
    "        res = []\n",
    "        for i, v in enumerate(ans):\n",
    "            if int(v[2]) > 1000:\n",
    "                res.append(\",\".join(v))\n",
    "                continue\n",
    "            for j, u in enumerate(ans):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if u[0] == v[0] and u[3] != v[3] and abs(int(v[1]) - int(u[1])) <= 60:\n",
    "                    res.append(\",\".join(v))\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Sort the transactions by time and iterate through them.\n",
    "    Use an array of size 60 to store the transactions in the last 60 minutes, where each slot stores the transactions for a specific minute,\n",
    "        in the form of a hash table mapping a name to a list of transactions.\n",
    "    '''\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        last_61 = [{} for _ in range(61)]\n",
    "        last_time = 0\n",
    "        \n",
    "        for i in range(len(transactions)):\n",
    "            transactions[i] = transactions[i].split(',')\n",
    "            transactions[i][1] = int(transactions[i][1])\n",
    "            transactions[i][2] = int(transactions[i][2])\n",
    "        transactions.sort(key=lambda x: x[1])\n",
    "\n",
    "        invalid_indices = set()\n",
    "        for i in range(len(transactions)):\n",
    "            name, time, amount, city = transactions[i]\n",
    "            if amount > 1000:\n",
    "                invalid_indices.add(i)\n",
    "\n",
    "            diff = min(time - last_time, 61) # diff seconds have passed since the last hit, so we should move the counter array forward by diff seconds\n",
    "            cur = (last_time % 61 + 1) % 61 # the index of the oldest timestamp in the counter array\n",
    "            for _ in range(diff):\n",
    "                last_61[cur] = {}\n",
    "                cur = (cur + 1) % 61\n",
    "            \n",
    "            for prev_transactions in last_61:\n",
    "                for j in prev_transactions.get(name, []):\n",
    "                    if transactions[j][3] != city:\n",
    "                        invalid_indices.add(i)\n",
    "                        invalid_indices.add(j)\n",
    "            \n",
    "            last_61[time % 61].setdefault(name, []).append(i)\n",
    "            last_time = time\n",
    "        \n",
    "        return [','.join(map(str, transactions[i])) for i in invalid_indices]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        \n",
    "        dct = defaultdict(list)\n",
    "        for ind, s in enumerate(transactions):\n",
    "            name, time, amount, city = s.split(\",\")\n",
    "            time = int(time)\n",
    "            amount = int(amount)\n",
    "            dct[name].append([name, time, amount, city, ind])\n",
    "        \n",
    "        ans = set()\n",
    "        for name in dct:\n",
    "            dct[name].sort(key=lambda x: x[1])\n",
    "            n = len(dct[name])\n",
    "            for i in range(n):\n",
    "                name, time, amount, city, ind = dct[name][i]\n",
    "                if amount > 1000:\n",
    "                    ans.add(ind)\n",
    "                    continue\n",
    "                    \n",
    "                for j in range(i-1, -1, -1):\n",
    "                    if time - dct[name][j][1] <= 60:\n",
    "                        if dct[name][j][-2] != city:\n",
    "                            ans.add(ind)\n",
    "                            break\n",
    "                    else:\n",
    "                        break\n",
    "                \n",
    "                for j in range(i+1, n):\n",
    "                    if dct[name][j][1] - time <= 60:\n",
    "                        if dct[name][j][-2] != city:\n",
    "                            ans.add(ind)\n",
    "                            break\n",
    "                    else:\n",
    "                        break\n",
    "        return [transactions[i] for i in ans]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        t = [x.split(',') for x in transactions]\n",
    "        res = []\n",
    "        for i in range(len(t)):  # 判断t[i] 是否是有效的\n",
    "            name, time, amount, city = t[i]\n",
    "            if int(amount) > 1000:\n",
    "                res.append(','.join(t[i]))\n",
    "                continue\n",
    "            for j, v in enumerate(t):\n",
    "                if j == i:\n",
    "                    continue\n",
    "                if (v[0] == name and v[3] != city and abs(int(time)-int(v[1])) <= 60):\n",
    "                    res.append(','.join(t[i]))\n",
    "                    break\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        hashmap = defaultdict(list)\n",
    "        for item in transactions:\n",
    "            name, time, pay, position = item.split(',')\n",
    "            valid = 1\n",
    "            if int(pay) > 1000:\n",
    "                valid = 0\n",
    "            hashmap[name].append([time, pay, position, valid])\n",
    "        ans = []\n",
    "        for key, values in hashmap.items():\n",
    "            values.sort(key=lambda x:int(x[0]))\n",
    "            n = len(values)\n",
    "            for i in range(n):\n",
    "                for j in range(i + 1, n):\n",
    "                    if int(values[j][0]) - int(values[i][0]) > 60:\n",
    "                        break\n",
    "                    if values[j][-2] != values[i][-2]:\n",
    "                        values[i][-1] = 0\n",
    "                        values[j][-1] = 0\n",
    "                if not values[i][-1]:\n",
    "                    ans.append(\",\".join([key] + values[i][:3]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        res = []\n",
    "        hashset = defaultdict(list)\n",
    "        for idx, val in enumerate(transactions):\n",
    "            temp = val.split(',')\n",
    "            name,time,money,city = temp[0],int(temp[1]),temp[2],temp[3]\n",
    "            if int(money) > 1000:\n",
    "                res.append(idx)\n",
    "            if name in hashset:\n",
    "                for values in hashset[name]:\n",
    "                    if abs(values[1] - time) <= 60 and values[2] != city:\n",
    "                        res.append(idx)\n",
    "                        res.append(values[0])\n",
    "            hashset[name].append([idx, time,city])\n",
    "        ans = []\n",
    "        for i in set(res):\n",
    "            ans.append(transactions[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\r\n",
    "        trans = [x.split(',') for x in transactions]\r\n",
    "        res = []\r\n",
    "        for i in range(len(trans)):\r\n",
    "            name, time, money, city = trans[i]\r\n",
    "            time = int(time)\r\n",
    "            if int(money) > 1000:\r\n",
    "                res.append(transactions[i])\r\n",
    "                continue\r\n",
    "            for j in range(len(trans)):\r\n",
    "                if i == j:\r\n",
    "                    continue\r\n",
    "                name1, time1, money1, city1 = trans[j]\r\n",
    "                if name1 == name and city1 != city and abs(int(time1) - time) <= 60:\r\n",
    "                    res.append(transactions[i])\r\n",
    "                    break\r\n",
    "        return res\r\n",
    "            \r\n",
    "\r\n",
    "\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        transactions=[i.split(\",\") for i in transactions]\n",
    "        res=[]\n",
    "        for i,v in enumerate(transactions):\n",
    "            if int(v[2])>1000:\n",
    "                res.append(\",\".join(v))\n",
    "                continue\n",
    "            for j,u in enumerate(transactions):\n",
    "                if i==j:\n",
    "                    continue\n",
    "                if v[0]==u[0] and v[3]!=u[3] and abs(int(v[1])-int(u[1]))<=60:\n",
    "                    res.append(\",\".join(v))\n",
    "                    break\n",
    "        return res            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        ans = []\n",
    "\n",
    "        tmp = []\n",
    "        n = len(transactions)\n",
    "        selected = [1] * n\n",
    "        for i, t in enumerate(transactions):\n",
    "            name, time, amount, city = t.split(',')\n",
    "            if int(amount) > 1000:\n",
    "                selected[i] = 0\n",
    "            tmp.append((name, time, amount, city))\n",
    "        transactions = tmp\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if transactions[i][0] == transactions[j][0] and abs(int(transactions[j][1]) - int(transactions[i][1])) <= 60 and transactions[i][3] != transactions[j][3]:\n",
    "                    selected[i] = selected[j] = 0\n",
    "        for i in range(n):\n",
    "            if not selected[i]:\n",
    "                ans.append(','.join(transactions[i]))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        t=[x.split(',') for x in transactions]\n",
    "        ans=[]\n",
    "        for i,ch in enumerate(t):\n",
    "            if int(ch[2])>1000:\n",
    "                ans.append(','.join(ch))\n",
    "                continue\n",
    "            for j,vals in enumerate(t):\n",
    "                if i==j:\n",
    "                    continue\n",
    "                elif ch[0]==vals[0] and abs(int(ch[1])-int(vals[1]))<=60 and ch[3]!=vals[3]:\n",
    "                    ans.append(','.join(ch))\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        # trans = [a.split(',') for a in transactions]\n",
    "        # res = []\n",
    "        # for i, val in enumerate(trans):\n",
    "        #     if int(val[2]) > 1000:\n",
    "        #         res.append(\",\".join(val))\n",
    "        #         continue\n",
    "        #     for j, u in enumerate(trans):\n",
    "        #         if i == j:\n",
    "        #             continue\n",
    "        #         if val[0] == u[0] and val[3]!=u[3] and abs(int(val[1])-int(u[1])) <= 60:\n",
    "        #             res.append(\",\".join(val))\n",
    "        # return res\n",
    "        transactions=[i.split(\",\") for i in transactions]\n",
    "        res=[]\n",
    "        for i,v in enumerate(transactions):\n",
    "            if int(v[2])>1000:\n",
    "                res.append(\",\".join(v))\n",
    "                continue\n",
    "            for j,u in enumerate(transactions):\n",
    "                if i==j:\n",
    "                    continue\n",
    "                if v[0]==u[0] and v[3]!=u[3] and abs(int(v[1])-int(u[1]))<=60:\n",
    "                    res.append(\",\".join(v))\n",
    "                    break\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        transactions_new = []\n",
    "        for i in range(len(transactions)):\n",
    "            temp = transactions[i].split(\",\") + [i]\n",
    "            temp[1] = int(temp[1])\n",
    "            temp[2] = int(temp[2])\n",
    "            transactions_new.append(temp)\n",
    "        transactions_new.sort(key=(lambda x: x[1]))\n",
    "\n",
    "        flags_inans = [False] * len(transactions_new)\n",
    "        ind_prev60 = 0\n",
    "        for i in range(len(transactions_new)):\n",
    "            transaction = transactions_new[i]\n",
    "            # 交易金额超过 $1000\n",
    "            if transaction[2] > 1000:\n",
    "                flags_inans[transactions_new[i][4]] = True\n",
    "            # 或者，它和 另一个城市 中 同名 的另一笔交易相隔不超过 60 分钟（包含 60 分钟整）\n",
    "            while transaction[1] > transactions_new[ind_prev60][1] + 60:\n",
    "                ind_prev60 += 1\n",
    "            \n",
    "            for j in range(ind_prev60, i):\n",
    "                tran2 = transactions_new[j]\n",
    "                if tran2[0] == transaction[0] and tran2[3] != transaction[3]:\n",
    "                    flags_inans[transactions_new[i][4]] = True\n",
    "                    flags_inans[transactions_new[j][4]] = True\n",
    "        \n",
    "        answer = []\n",
    "        for i in range(len(transactions)):\n",
    "            if flags_inans[i]:\n",
    "                answer.append(transactions[i])\n",
    "        return answer\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    Build a hash table that maps (time, name) to the cities of the transactions that happened at the given time and by the given person.\n",
    "    Then for each transaction, check if it is invalid:\n",
    "        1. If the amount is greater than 1000, it is invalid.\n",
    "        2. If there is another transaction by the same person within 60 minutes and in a different city, it is invalid.\n",
    "    Time complexity: O(n). Space complexity: O(n).\n",
    "    '''\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        mapping = {}\n",
    "        for transaction in transactions:\n",
    "            name, time, _, city = transaction.split(',')\n",
    "            time = int(time)\n",
    "            mapping.setdefault((time, name), set()).add(city) # use set to avoid duplicates\n",
    "        \n",
    "        invalid = []\n",
    "        for transaction in transactions:\n",
    "            name, time, amount, city = transaction.split(',')\n",
    "            time, amount = int(time), int(amount)\n",
    "            if amount > 1000:\n",
    "                invalid.append(transaction)\n",
    "                continue\n",
    "\n",
    "            for other_time in range(time - 60, time + 61):\n",
    "                if (other_time, name) not in mapping:\n",
    "                    continue\n",
    "                if (len(mapping[(other_time, name)]) > 1 or # the set contains more than one element -> there are transactions in different cities\n",
    "                    next(iter(mapping[(other_time, name)])) != city): # get the only element in the set\n",
    "                    invalid.append(transaction)\n",
    "                    break\n",
    "        return invalid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        h = defaultdict(list) # [idx]\n",
    "        tmp = [i.split(',') for i in transactions]\n",
    "        for idx, v in enumerate(tmp):\n",
    "            h[v[0]].append(idx)\n",
    "        st = set()\n",
    "        for k, v in h.items():\n",
    "            for i in range(len(v)):\n",
    "                if int(tmp[v[i]][2]) > 1000:\n",
    "                    st.add(v[i])\n",
    "                idx1 = v[i]\n",
    "                for j in range(i + 1, len(v)):\n",
    "                    idx2 = v[j]\n",
    "                    if tmp[idx1][3] != tmp[idx2][3] and abs(int(tmp[idx1][1]) - int(tmp[idx2][1])) <= 60:\n",
    "                        st.add(idx1)\n",
    "                        st.add(idx2)\n",
    "        return [transactions[i] for i in st]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        #转换列表\n",
    "        trans = [i.split(',') for i in transactions]\n",
    "        ans = []\n",
    "        lens = len(transactions)\n",
    "        for i in range(lens):\n",
    "            namei,timei,amounti,cityi = trans[i]\n",
    "            if int(amounti) > 1000:\n",
    "                ans.append(transactions[i])\n",
    "                continue\n",
    "            for j in range(lens):\n",
    "                if i == j: #仅当遍历到自身的时候跳过\n",
    "                    continue\n",
    "                namej,timej,amountj,cityj = trans[j]\n",
    "                if namei == namej and cityi != cityj and abs(int(timei) - int(timej)) <=60 :\n",
    "                    ans.append(transactions[i])\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        no_effect_list=[]\n",
    "        name_list=[]\n",
    "        time_list=[]\n",
    "        amount_list=[]\n",
    "        city_list=[]\n",
    "        l=len(transactions)\n",
    "        for i in range(0,l):\n",
    "            ll=list(transactions[i].strip().split(','))\n",
    "            name_list.append(ll[0])\n",
    "            ll[1]=int(ll[1])\n",
    "            time_list.append(ll[1])\n",
    "            ll[2]=int(ll[2])\n",
    "            amount_list.append(ll[2])\n",
    "            city_list.append(ll[3])\n",
    "        for i in range(l):\n",
    "            for j in range(i+1,l):\n",
    "                if name_list[i]==name_list[j] and city_list[i] != city_list[j] and abs(time_list[i]-time_list[j])<=60:\n",
    "                    no_effect_list.append(transactions[i])\n",
    "                    no_effect_list.append(transactions[j])\n",
    "        for i in range(l):\n",
    "            if amount_list[i] > 1000 and transactions[i]:\n",
    "                no_effect_list.append(transactions[i])\n",
    "        buc_list=[]\n",
    "        no_effect_list=list(set(no_effect_list))\n",
    "        for i in range(len(no_effect_list)):\n",
    "            if transactions.count(no_effect_list[i])>1:\n",
    "                ct=transactions.count(no_effect_list[i])\n",
    "                for j in range(ct-1):\n",
    "                    buc_list.append(no_effect_list[i])\n",
    "        \n",
    "        no_effect_list=no_effect_list+buc_list\n",
    "        return no_effect_list\n",
    "\n",
    "\n",
    "         \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        unavil = []\n",
    "        transplt = []\n",
    "        for i in range(0,len(transactions)):\n",
    "            splt = transactions[i].split(',')\n",
    "            splt.append('T')\n",
    "            transplt.append(splt)\n",
    "            if int(splt[2]) > 1000 and splt[4] == 'T':\n",
    "                splt[4] = 'F'\n",
    "                unavil.append(transactions[i])\n",
    "        for trans in range(0,len(transplt)-1):\n",
    "            for check in range(trans+1,len(transplt)):\n",
    "                if transplt[trans][0] == transplt[check][0] and transplt[trans][3] != transplt[check][3] and abs(int(transplt[check][1]) - int(transplt[trans][1])) <= 60:\n",
    "                    if transplt[trans][4] == 'T':\n",
    "                        transplt[trans][4] = 'F'\n",
    "                        unavil.append(transactions[trans])\n",
    "                    if transplt[check][4] == 'T':\n",
    "                        transplt[check][4] = 'F'\n",
    "                        unavil.append(transactions[check])\n",
    "        print(transplt)\n",
    "        return unavil"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        result = []\n",
    "        name_value_mapping = collections.defaultdict(lambda: [])\n",
    "        for tran in transactions:\n",
    "            name, time, amount, loc = tran.split(',')\n",
    "            name_value_mapping[name].append([name, time, amount, loc])\n",
    "\n",
    "        for name, trans in name_value_mapping.items():\n",
    "            for i in range(len(trans)):\n",
    "                if int(trans[i][2]) > 1000:\n",
    "                    result.append(trans[i])\n",
    "                    continue\n",
    "                for j in range(len(trans)):\n",
    "                    if i == j:\n",
    "                        continue\n",
    "                    if abs(int(trans[i][1]) - int(trans[j][1])) <= 60 and trans[i][3] != trans[j][3]:\n",
    "                        result.append(trans[i])\n",
    "                        break\n",
    "\n",
    "        result = [\",\".join(i) for i in result]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        transactions = [i.split(',') for i in transactions]\n",
    "        res = []\n",
    "        for i, tran in enumerate(transactions):\n",
    "            if int(tran[2]) > 1000:\n",
    "                res.append(\",\".join(tran))\n",
    "                continue\n",
    "            for j, tran_ in enumerate(transactions):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if tran[0] == tran_[0] and tran[3] != tran_[3] and abs(int(tran[1]) - int(tran_[1])) <= 60:\n",
    "                    res.append(\",\".join(tran))\n",
    "                    break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        result = []\n",
    "        name_value_mapping = collections.defaultdict(list)\n",
    "        for tran in transactions:\n",
    "            name, time, amount, loc = tran.split(',')\n",
    "            name_value_mapping[name].append([name, time, amount, loc])\n",
    "\n",
    "        for name, trans in name_value_mapping.items():\n",
    "            for i in range(len(trans)):\n",
    "                if int(trans[i][2]) > 1000:\n",
    "                    result.append(trans[i])\n",
    "                    continue\n",
    "                for j in range(len(trans)):\n",
    "                    if i == j:\n",
    "                        continue\n",
    "                    if abs(int(trans[i][1]) - int(trans[j][1])) <= 60 and trans[i][3] != trans[j][3]:\n",
    "                        result.append(trans[i])\n",
    "                        break\n",
    "\n",
    "        result = [\",\".join(i) for i in result]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        n = len(transactions)\n",
    "        transactionsN = []\n",
    "        for transaction in transactions:\n",
    "            tmp = transaction.split(',')\n",
    "            transactionsN.append(tmp)\n",
    "        transactionsN.sort(key=lambda x: (x[0],int(x[1])))\n",
    "        visited = set()\n",
    "        idx = 0\n",
    "        ans = []\n",
    "        while idx < n:\n",
    "            if idx == 0:\n",
    "                if int(transactionsN[idx][2]) > 1000:\n",
    "                    res = ','.join(transactionsN[idx])\n",
    "                    ans.append(res)\n",
    "                    visited.add(idx)\n",
    "            elif transactionsN[idx][0] == transactionsN[idx-1][0] and int(transactionsN[idx][1]) - int(transactionsN[idx-1][1]) <= 60:\n",
    "                if int(transactionsN[idx][2]) > 1000:\n",
    "                    ans.append(','.join(transactionsN[idx]))\n",
    "                    visited.add(idx)\n",
    "                j = 1\n",
    "                while idx-j >=0:\n",
    "                    if transactionsN[idx][0] == transactionsN[idx-j][0] and int(transactionsN[idx][1]) - int(transactionsN[idx-j][1]) <= 60:\n",
    "                        if transactionsN[idx][3] != transactionsN[idx-j][3]:\n",
    "                            if idx not in visited:\n",
    "                                res = ','.join(transactionsN[idx])\n",
    "                                ans.append(res)\n",
    "                                visited.add(idx)\n",
    "                            res = ','.join(transactionsN[idx-j])\n",
    "                            if idx-j not in visited:\n",
    "                                ans.append(res)\n",
    "                                visited.add(idx-j)\n",
    "                    else:\n",
    "                        break\n",
    "                    j += 1\n",
    "            elif int(transactionsN[idx][2]) > 1000:\n",
    "                    ans.append(','.join(transactionsN[idx]))\n",
    "                    visited.add(idx)\n",
    "            idx += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        n = len(transactions)\n",
    "        transactionsN = []\n",
    "        for transaction in transactions:\n",
    "            tmp = transaction.split(',')\n",
    "            transactionsN.append(tmp)\n",
    "        transactionsN.sort(key=lambda x: (x[0],int(x[1])))\n",
    "        visited = set()\n",
    "        idx = 0\n",
    "        ans = []\n",
    "        while idx < n:\n",
    "            if idx == 0:\n",
    "                if int(transactionsN[idx][2]) > 1000:\n",
    "                    ans.append(','.join(transactionsN[idx]))\n",
    "                    visited.add(idx)\n",
    "            elif transactionsN[idx][0] == transactionsN[idx-1][0] and int(transactionsN[idx][1]) - int(transactionsN[idx-1][1]) <= 60:\n",
    "                if int(transactionsN[idx][2]) > 1000:\n",
    "                    ans.append(','.join(transactionsN[idx]))\n",
    "                    visited.add(idx)\n",
    "                j = 1\n",
    "                while idx-j >=0:\n",
    "                    if transactionsN[idx][0] == transactionsN[idx-j][0] and int(transactionsN[idx][1]) - int(transactionsN[idx-j][1]) <= 60:\n",
    "                        if transactionsN[idx][3] != transactionsN[idx-j][3]:\n",
    "                            if idx not in visited:\n",
    "                                ans.append(','.join(transactionsN[idx]))\n",
    "                                visited.add(idx)\n",
    "                            if idx-j not in visited:\n",
    "                                ans.append(','.join(transactionsN[idx-j]))\n",
    "                                visited.add(idx-j)\n",
    "                    else:\n",
    "                        break\n",
    "                    j += 1\n",
    "            elif int(transactionsN[idx][2]) > 1000:\n",
    "                    ans.append(','.join(transactionsN[idx]))\n",
    "                    visited.add(idx)\n",
    "            idx += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        lst=[]\n",
    "        for i in transactions:\n",
    "            lst.append(i.split(','))\n",
    "        lst=sorted(lst,key=lambda x:int(x[1]))\n",
    "       \n",
    "        question=set()\n",
    "        dic={}\n",
    "        for i in range(len(lst)):\n",
    "            j=lst[i]\n",
    "            if int(j[2])>1000:\n",
    "                question.add(i)\n",
    "            \n",
    "            if j[0] not in dic:\n",
    "                dic[j[0]]=[(int(j[1]),i,j[3])]\n",
    "            else:\n",
    "                dic[j[0]].append((int(j[1]),i,j[3]))\n",
    "            \n",
    "        for i in dic:\n",
    "            t=sorted(dic[i],key=lambda x:x[0])\n",
    "            for i in range(1,len(t)):\n",
    "                for j in range(i):\n",
    "                    if t[i][0]-t[j][0]<=60 and t[i][2]!=t[j][2]:\n",
    "                        question.add(t[i][1])\n",
    "                        question.add(t[j][1])\n",
    "        ans=[]\n",
    "        for i in question:\n",
    "            ans.append(','.join(lst[i]))\n",
    "        return ans         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        lst=[]\n",
    "        for i in transactions:\n",
    "            lst.append(i.split(','))\n",
    "        lst=sorted(lst,key=lambda x:int(x[1]))\n",
    "       \n",
    "        question=set()\n",
    "        dic={}\n",
    "        for i in range(len(lst)):\n",
    "            j=lst[i]\n",
    "            if int(j[2])>1000:\n",
    "                question.add(i)\n",
    "            \n",
    "            if j[0] not in dic:\n",
    "                dic[j[0]]=[(int(j[1]),i,j[3])]\n",
    "            else:\n",
    "                dic[j[0]].append((int(j[1]),i,j[3]))\n",
    "            \n",
    "        for i in dic:\n",
    "            t=sorted(dic[i],key=lambda x:x[0])\n",
    "            for i in range(1,len(t)):\n",
    "                for j in range(i):\n",
    "                    if t[i][0]-t[j][0]<=60 and t[i][2]!=t[j][2]:\n",
    "                        question.add(t[i][1])\n",
    "                        question.add(t[j][1])\n",
    "        ans=[]\n",
    "        for i in question:\n",
    "            ans.append(','.join(lst[i]))\n",
    "        return ans                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        transactions = [term.split(',') for term in transactions]\n",
    "        transactions = [(term[0], int(term[1]), int(term[2]), term[3]) for term in transactions]\n",
    "\n",
    "        trans_dict = {}\n",
    "        for term in transactions:\n",
    "            if term[0] not in trans_dict:\n",
    "                trans_dict[term[0]] = []\n",
    "            trans_dict[term[0]].append(term)\n",
    "        \n",
    "        ans = []\n",
    "        for term in transactions:\n",
    "            name, time, money, city = term\n",
    "            if money > 1000:\n",
    "                ans.append(f'{name},{time},{money},{city}')\n",
    "                continue\n",
    "            for name_term in trans_dict[name]:\n",
    "                if name_term[-1] != city and abs(name_term[1] - time) <= 60:\n",
    "                    ans.append(f'{name},{time},{money},{city}')\n",
    "                    break\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        transactions=[i.split(\",\") for i in transactions]\n",
    "        res=[]\n",
    "        for i,v in enumerate(transactions):\n",
    "            if int(v[2])>1000:\n",
    "                res.append(\",\".join(v))\n",
    "                continue\n",
    "            for j,u in enumerate(transactions):\n",
    "                if i==j:\n",
    "                    continue\n",
    "                if v[0]==u[0] and v[3]!=u[3] and abs(int(v[1])-int(u[1]))<=60:\n",
    "                    res.append(\",\".join(v))\n",
    "                    break\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def invalidTransactions(self, transactions: List[str]) -> List[str]:\n",
    "        lst = []\n",
    "\n",
    "        for i in transactions:\n",
    "            lst.append(i.split(','))\n",
    "        \n",
    "        lst = sorted(lst,key=lambda x:int(x[1]))\n",
    "\n",
    "        question = set()\n",
    "        dic = {}\n",
    "\n",
    "        for i in range(len(lst)):\n",
    "            j = lst[i]\n",
    "            if int(j[2])>=1000:\n",
    "                question.add(i)\n",
    "            \n",
    "            if j[0] not in dic:\n",
    "                dic[j[0]] = [(int(j[1]),i,j[3])]\n",
    "            else:\n",
    "                dic[j[0]].append((int(j[1]),i,j[3]))\n",
    "        \n",
    "        for i in dic:\n",
    "            t = sorted(dic[i],key = lambda x:x[0])\n",
    "            for i in range(1,len(t)):\n",
    "                for j in range(i):\n",
    "                    if t[i][0]-t[j][0]<=60 and t[i][2]!=t[j][2]:\n",
    "                        question.add(t[i][1])\n",
    "                        question.add(t[j][1])\n",
    "        \n",
    "        ans = []\n",
    "        for i in question:\n",
    "            ans.append(','.join(lst[i]))\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
